「ZJOI2019模拟赛 六」硬币

模拟赛爆炸祭QwQ…

题面

硬币

coin.cpp

coin.in/.out

时间限制:1s

空间限制:512M

题目描述

KK有一枚硬币，他想做如下实验：

他会不停抛掷这枚硬币，并且记录下每次硬币是哪面朝上，当出现连续两次都是正面朝上时，就停止实验。

设总共抛掷了 $M$ 次后停止实验（即第 $M$ 次和第 $M-1$ 次都是正面朝上，而之前没有出现过连续两次正面朝上），令 $P(n)$ 表示 $M$ 是 $n$ 的倍数的概率。

比如 $P(2)={3\over 5}，P(3)={9\over 31}$，可以发现 $P(n)$ 总是可以表示成一个分数。

现在KK想知道 $P(n)$ 对 $10^9+9$ 取模后的结果。

输入格式

一行，一个数 $n$。

输出格式

一行，表示 $P(n)$ 对 $10^9+9$ 取模后的结果。

样例数据

input1

output1

548387102

input2

output2

618264982

input3

1	100000000000000000

output3

346869049

数据规模与约定

对于 $30\%$ 的数据 $n\le 100$

对于 $50\%$ 的数据 $n\le 1000000$

对于 $80\%$ 的数据 $n\le 1000000000$

对于 $100\%$ 的数据 $n\le 10^{18}$

小贴士

对于 ${n\over m}$ 及一个质数 $p$，${n\over m}$ 在模 $p$ 意义下等于 $n\times m^{p-2}$

$\sqrt{5}$在模$10^9+9$的意义下的值为$383008016$。

题解

这道题基本上就没有部分分，做出来了就100，否则就0分。然而蒟蒻我还是太菜了，所以我必定属于后者。~~然后这场模拟赛我就光荣地爆炸了QwQ~~

这题推起来其实挺烦的，但是在省选题里面好像应该算简单了的吧。看来我还是太菜了。

废话不多说，接下来马上进入愉快的推式子环节。~~woc哪里愉快了~~

设$C(i)$表示抛了$i$次硬币，没有连续两次正面朝上的方案数。

令$1$表示正面朝上，$0$表示反面朝上，那么$C(i)$也就是长度为$i$的不存在连续两个$1$的01串的个数。

假设我们已近求出了$C(i-1)$和$C(i-2)$，现在考虑如何来计算出$C(i)$的值。比如$i=3$。

长度为$2$的串一共有$4$个，分别是00、01、10、11，其中串11是不合法的，其余的都是合法的。把这些串复制两份，一份前面加0，一次前面加1，这样就能得到长度为3的8个01串。

如果再前面加0，那么原来合法的串依然合法，原来不合法的串依然不合法。所以可以先把$C(i-1)$先累加到$C(i)$上。

如果在前面加1，那么原来以1开头的串就都不合法了，原来以0开头的串合法性不变。原来一共有$C(i-2)$个0开头的合法串，这些串同样也要累加到$C(i)$上。

所以就有递推式：$C(i)=C(i-1)+C(i-2)$，其中$C(1)=2,C(2)=3$。所以这就是一个错了2位的斐波那契数列。

再设$F(i)$表示抛了$i$次硬币，恰好结束的概率。

那么就有$F(i)=\frac{C(i-3)}{2^{i-3}}*\frac{1}{8}$。因为当且仅当前$i-3$次都要合法，第$i-2$反面朝上，最后两次都正面朝上才会停止。

所以

$F(i)=\frac{C(i-3)}{2^{i-3}}*\frac{1}{8}=\frac{C(i-3)}{2^i}=\frac{Fib(i-1)}{2^i}$

再根据题意，可得

$P(n)=F(n)+F(2n)+\cdots+F(\infty n)=\sum_{i=1}^{\infty}{\frac{Fib(in-1)}{2^{in}}}$

其中斐波那契数列有一个通项公式

$Fib(n)=\frac{\sqrt{5}}{5}((\frac{1+\sqrt{5}}{2})^n-(\frac{1-\sqrt{5}}{2})^n)$

再设

$\alpha=\frac{1+\sqrt{5}}{2},\beta=\frac{1-\sqrt{5}}{2}$

所以

$P(n)=\sum_{i=1}^{\infty}{\frac{Fib(in-1)}{2^{in}}}= \sum_{i=1}^{\infty}{\frac{\sqrt{5}}{5}\cdot\frac{\alpha^{in-1}-\beta^{in-1}}{2^{in}}}$

然后发现上面那个式子并不好处理，再化简一下

$\sum_{i=1}^{\infty}{\frac{\sqrt{5}}{5}\cdot\frac{\alpha^{in-1}-\beta^{in-1}}{2^{in}}}= \frac{\sqrt{5}}{5}\sum_{i=1}^{\infty}{\frac{\alpha^{in-1}}{2^{in}}}-\frac{\sqrt{5}}{5}\sum_{i=1}^{\infty}{\frac{\beta^{in-1}}{2^{in}}}= \frac{\sum_{i=1}^{\infty}{\frac{\alpha^{in-1}}{2^{in}}}- \sum_{i=1}^{\infty}{\frac{\beta^{in-1}}{2^{in}}}}{\sqrt{5}}$

回想一下，发现带有无穷的式子可以通过等比数列还搞，于是想办法把上式搞出等比数列

$上式=\frac{\frac{1}{\alpha}\sum_{i=1}^{\infty}{\frac{\alpha^{in}}{2^{in}}}- \frac{1}{\beta}\sum_{i=1}^{\infty}{\frac{\beta^{in}}{2^{in}}}}{\sqrt{5}}$

然后$\sum{i=1}^{\infty}{\frac{\alpha^{in}}{2^{in}}}$就是等比数列，想办法把它的值算出来，后面的$\sum{i=1}^{\infty}{\frac{\beta^{in}}{2^{in}}}$也一样的。

$\sum_{i=1}^{\infty}{\frac{\alpha^{in}}{2^{in}}}=\sum_{i=1}^{\infty}{(\frac{\alpha^{n}}{2^{n}})^{i}}\\ 设q=\frac{\alpha^{n}}{2^{n}}\\ 设S=\sum_{i=1}^{\infty}{(\frac{\alpha^{n}}{2^{n}})^{i}}=q^1+q^2+q^3+\cdots+q^{\infty}\\ 则qS=q^2+q^3+q^4+\cdots+q^{\infty}\\ 故(q-1)S=-q\\ S=\frac{q}{1-q}$

求出$S$之后再代回原始中就能求出$P(n)$的值了。

终于写完了QwQ…

代码

推了一长串，代码是真的短QwQ

#include<cmath>
#include<cstdio>
using namespace std;
typedef long long LL;
const LL TT=1000000009,sqrt5=383008016,inv2=500000005;
LL n;
LL QP(LL a,LL b)
{
	LL ret=1,w=a;
	while(b)
	{
		if(b&1) ret=ret*w%TT;
		w=w*w%TT;b>>=1;
	}
	return ret;
}
LL Sum(LL q)
{
	q=QP(q,n);
	return q*QP((1-q+TT)%TT,TT-2)%TT;
}
int main()
{
	freopen("coin.in","r",stdin);
	freopen("coin.out","w",stdout);
	scanf("%lld",&n);
	LL alpha=(1+sqrt5)*inv2%TT,beta=(1+TT-sqrt5)*inv2%TT;
	printf("%lld\n",(QP(sqrt5,TT-2)*(QP(alpha,TT-2)*Sum(alpha*inv2%TT)%TT-QP(beta,TT-2)*Sum(beta*inv2%TT)%TT)%TT+TT)%TT);
	return 0; 
}